Ink jet printers using an array of multiple nozzles have been available for years, as have other types of printers using an array of multiple printing devices such as light emitting diodes (LEDs). In such printers, these nozzles are typically grouped together on a printhead, which typically is affixed to a moveable carriage or carrier that moves left and right in a horizontal manner with respect to a sheet of paper that is moving or indexing in a perpendicular, vertical direction. The multiple nozzles (or LEDs) are typically grouped in a vertical column (or multiple such vertical columns) so that, on one horizontal pass of the printhead via its carrier, multiple horizontal "columns" of dots or pels (i.e., print elements), can be simultaneously laid down in a "swath" of ink upon the paper or other print media.
As the printhead travels in the horizontal direction, it produces tiny dots along the swath according to "print data" that has been received by the printer, typically from a host computer. The "width" (i.e., "height," in this orientation) of the swath is dependent upon the resolution of the printhead nozzles (such as 300 dpi (dots per inch)), which is 1/300 inch resolution, as well as the number of nozzles in the vertical column array on the printhead. If, for example, the printhead has an array of 104 nozzles, and its resolution is 300 dpi, then the swath would be approximately 1/3 inch in width. Typical conventional printers format the print data so that each of the nozzles receives a digital (i.e., either "on" or "off") datum bit of information virtually simultaneously, which means that, in the above example, a data set of at least 104 bits must be sent to the printhead to control the 104 nozzles that are ready to either print a dot by turning ON (e.g., Logic 1), or to not print a dot which would be the nozzle's OFF state (e.g., Logic 0). This data set for a particular instant of time to control the entire vertical column array of 104 nozzles is designated by the term "slice." Therefore, to create a swath of print data, slice after slice of print data must be sent to the printhead to sequentially turn ON or OFF each of the printhead's nozzles at the correct times to reproduce the print data pattern representation that was earlier received by the printer from its host computer. In the above example, each slice must contain 104 bits of print data and, assuming that the horizontal resolution was also 300 dpi, there would then have to be 300 slices of data per horizontal inch of printhead travel via its carrier, thereby creating a rectangle of 104.times.300 pels, or 1/3 inch.times.1 inch.
In conventional ink jet printers, it is typical to import print data from a host PC and to store that print data by receiving "words" or "bytes" of print data, where each bit of the word or byte represents a single pel once the data is in the form of a "bitmap." Bitmap information typically arrives as a series of words of sixteen (16) bits each until a complete slice has been defined. Once the first slice of a swath has been received and stored in the printer's memory system, additional words are then received to define the next consecutive slice, and this procedure continues until all of the slices for a swath have been received and then stored in the printer's memory system. After the first swath has been completed, the subsequently received print data will again be in groupings of words to define the first slice of the next swath, which typically is the adjacent swath to the one that has just been completed.
This process continues until all of the slices for all of the swaths have been received for an entire page to be printed. If no data compression or data compacting techniques are used, the bitmap received by the printer and subsequently stored in the printer's memory system will represent a series of vertical slices adjacent to one another to make up a swath, and a series of horizontal swaths that are adjacent to one another to define the entire vertical structure of the page to be printed. All of these slices and swaths are composed of individual pels, whether or not these pels are to be printed or to be blank, thereby forming an entire rectangular page of bitmap print data. This approach is very memory intensive, because all of the "blank" areas where there are no pels to be printed nevertheless require the same amount of memory space as areas that have various pels being printed by the printhead. Without any type of data compression or data compacting techniques, the amount of memory area required to store a single page of print data will always be the number of pels required to make up all of the slices of each swath times the number of swaths for that page. For example, if an entire 81/2.times.11 inch page of print data were to be stored in memory, at 300 dpi there would be (8.5.times.300).times.(11.times.300)=8,415,000 pels required. This roughly eight million bits of data would correspond to just over one million bytes of memory space required in the printer's memory system, and that is assuming no extra bits are used for any (typical) error checking routines. It is easy to see that there are advantages to reducing the amount of memory space required to hold print data in such printing systems.
In a patent by Bauman (U.S. Pat. No. 5,272,768), a data compression technique is disclosed that compresses character font data, then stores that compressed font character, and later decompresses the font character just before it is printed by a printhead. This Bauman data compression technique is typically used by an ink jet printer or perhaps by a printer using an array of LEDs, in which the rows to be printed are grouped in horizontal swaths. In one example provided in Bauman, each character comprises three (3) swaths of data, designated as "strips." Each of these strips is comprised of 16 bits or pels of print data, and each character font is analyzed to see if it requires all three (3) strips to be defined as containing at least one pel of "black" or printed data. If so, then that particular character's font is not compressed. On the other hand, if one or more of these strips is entirely blank for a particular character font, then that character is compressed by deleting the one or more strips that are not required to print that character. The printer's font ROM (i.e., read only memory) stores these character fonts in their compressed state, thereby saving some memory space within the font ROM.
As disclosed in Bauman, the print job data is received from a host computer and temporarily stored in an input buffer. This data would typically be ASCII data at this point, and not bitmap data. In these situations, the ASCII data must be interpreted or "RIPed" (i.e., undergo raster image processing), so that each character will have a bitmap created for it by the font ROM. Somewhere within the printer, the character must become a bitmap image before being sent to the print engine. In Bauman, as the ASCII characters arrive at the printer, for each font that is available in the printer's font ROM, such ASCII characters will be converted into a bitmap by use of the compressed image stored in the font ROM, which then must be uncompressed by the printer before being sent to the print engine. This is achieved by keeping track as to which of the three strips for each particular character font has been deleted to create the compressed font for that ASCII character. A data table is used to store this information, and when the bitmap is created for that particular character font, the "deleted" strip is then added to the bitmap of the entire character before being sent to the print engine. The Bauman invention works only with pre-determined character data, such as alphanumeric characters of different type font and point size, and which is imported into the printer as ASCII data or some other high level language data format.
Another U.S. patent, by Nagata (U.S. Pat. No. 5,237,645), discloses a printer that uses a light-emitting diode (LED) array, or a laser head or other similar device. Typical conventional laser printers do not print data in swaths, but instead by individual rows of single pels. If an array of LEDs is used, then the printing process can be done in swaths. In either case, Nagata teaches a method for compressing bitmap data before such data is stored in image memory. The print data is either received as already bitmapped data, or it arrives from a host computer in some type of high level page description language, such as PostScript.TM.. If the data arrives in a high level language, then a bitmap must first be created by RIPing the data. Once the data is in a bitmap format, Nagata receives an entire page of data in an uncompressed state into a virtual page of memory. At this point, the entire page of data is divided into "virtual blocks," and this essentially is done by choosing a block size. Once the virtual block size has been chosen, the Nagata system must RIP enough "rasters" (i.e., lines that are one (1) pixel or pel in height) until there are enough to fill the entire height of a block (which now consists of a partial bitmap). Once these blocks have been determined, the Nagata printer analyzes each of the virtual blocks to decide whether or not any of the blocks are completely blank (i.e., containing no data to be printed within that particular area). Such blank blocks are designated as "empty" blocks. All non-empty blocks are then designated as "effective" blocks. Only effective blocks are stored in the image memory, although the location for each empty block is stored in a different set of memory registers. In this manner, a large amount of image memory can potentially be saved for each page of data to be printed.
By compressing the data according to the Nagata invention, more than one page of print data typically can fit within the limited space available in the image memory. Of course, this compressed data must later be uncompressed before being sent to the print engine. According to Nagata, the effective blocks are retrieved from image memory as needed in full bitmap format, per each raster section as required. When the printer arrives at an empty block, such raster sections are merely loaded with zeros to provide print data for the block, and then that data is transferred to the print engine. In this manner, the print engine always receives full bitmap data for the entire page to be printed. Accordingly, the print engine must physically pass over every physical pel location of the page to be printed, regardless of whether or not a pel is to be printed at that location. It will take the print engine just as long to "print" a large area of blank data as it would for that print engine to lay down black pels in various places upon an equivalent area of the page.
In U.S. Pat. No. 3,827,357 (by Mahoney), a printer is disclosed which stores an entire character at each line/column position. If the character is a blank or is an unprintable character (e.g., for some type of invalid code), then that character will not be printed. As each line of data is stored, a counter is decremented for each byte (i.e., character) that can be printed. During printing, the counter is again decremented for each character until it has been determined that all printable characters for this line have been printed. At that point, the rest of the line is abandoned, and the printer shifts its printhead immediately to the next line. Mahoney is an older patent that was primarily directed toward dot matrix or formed character printers. Mahoney essentially discloses one method for determining the right-most character of each line, and when that character has been reached by the printhead, then a line feed can immediately be commanded to occur.
Another example of a conventional ink jet printer is disclosed in Bohrer (U.S. Pat. No. 4,481,602). Bohrer essentially discloses a method for compressing font data before being stored in memory, then later decompresses that data before printing. Bohrer professes to use a method that minimizes the size of the pointer table to provide an overall three-times storage compression. As related above, any appreciable storage compression is valuable, because one can store more than a single page of print data into an image buffer that may have been designed to hold only one (uncompressed) page of print data in bitmap form, thereby increasing printing overall speed by more efficiently processing the print data. Of course, the Bohrer printer must perform a large amount of data manipulation to achieve its stated goal. According to the Bohrer method, each character is matched with its particular font, and a pointer and correction factor offset is created for each of these characters. This information is stored in a "scroll array" of compressed data and also in a "pointer table." When it is time to uncompress the data, the size of the character must be found in the scroll array, the position of the character in its "fall character box" must be determined, and the character is then copied into the bitmap, utilizing all of the stored data including the pointer and the correction factor offset. While Bohrer may save memory space in the image table, it also requires a large amount of processing that may slow down the overall printing procedure.
While data compression techniques have desirable features, it would also be desirable to "compact" print data in a manner that will not later require a decompression operation. While compacting this data, certain blank areas could be removed from the image memory table so that a significant amount of memory space is saved. By eliminating the requirement for first compressing and then later decompressing the data, processing time within the printer will be improved. Furthermore, such a procedure could be used on graphical data, not merely pre-determined character (i.e., font) data.